from typing import List


class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        dirs = [[0,1], [1, 0], [0,-1],[-1, 0]]
        rows = len(board)
        cols = len(board[0])
        visited = [[False for _ in range(cols)] for _ in range(rows)]
  
        def dfs(row, col, index, visite)->bool:
            if board[row][col]!=word[index]:
                return False

            if index == len(word)-1:
                return True

            visite[row][col] = True
            res = False

            for dir in dirs:
                next_row = row + dir[0]
                next_col = col + dir[1]
                
                if next_row>=0 and next_row<rows and next_col>=0 and next_col<cols and not visite[next_row][next_col]:
                    res = dfs(next_row, next_col, index+1, visited)
                    if res:
                        break

            visite[row][col] = False

            return res

        for row in range(rows):
            for col in range(cols):
                if board[row][col]==word[0]:
                    flag = dfs(row, col, 0, visited)
                    if flag:
                        return True


        return False


if __name__ == '__main__':
    s = Solution().exist([["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], "ABCCED")        


        